{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Ways to Form a Target String Given a Dictionary"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numWays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #通过给定词典构造目标字符串的方案数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串列表 <code>words</code> 和一个目标字符串 <code>target</code> 。<code>words</code> 中所有字符串都 <strong>长度相同</strong>  。</p>\n",
    "\n",
    "<p>你的目标是使用给定的 <code>words</code> 字符串列表按照下述规则构造 <code>target</code> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>从左到右依次构造 <code>target</code> 的每一个字符。</li>\n",
    "\t<li>为了得到 <code>target</code> 第 <code>i</code> 个字符（下标从 <strong>0</strong> 开始），当 <code>target[i] = words[j][k]</code> 时，你可以使用 <code>words</code> 列表中第 <code>j</code> 个字符串的第 <code>k</code> 个字符。</li>\n",
    "\t<li>一旦你使用了 <code>words</code> 中第 <code>j</code> 个字符串的第 <code>k</code> 个字符，你不能再使用 <code>words</code> 字符串列表中任意单词的第 <code>x</code> 个字符（<code>x <= k</code>）。也就是说，所有单词下标小于等于 <code>k</code> 的字符都不能再被使用。</li>\n",
    "\t<li>请你重复此过程直到得到目标字符串 <code>target</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p><strong>请注意</strong>， 在构造目标字符串的过程中，你可以按照上述规定使用 <code>words</code> 列表中 <strong>同一个字符串</strong> 的 <strong>多个字符</strong> 。</p>\n",
    "\n",
    "<p>请你返回使用 <code>words</code> 构造 <code>target</code> 的方案数。由于答案可能会很大，请对 <code>10<sup>9</sup> + 7</code> <strong>取余</strong> 后返回。</p>\n",
    "\n",
    "<p>（译者注：此题目求的是有多少个不同的 <code>k</code> 序列，详情请见示例。）</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>words = [\"acca\",\"bbbb\",\"caca\"], target = \"aba\"\n",
    "<b>输出：</b>6\n",
    "<b>解释：</b>总共有 6 种方法构造目标串。\n",
    "\"aba\" -> 下标为 0 (\"<strong>a</strong>cca\")，下标为 1 (\"b<strong>b</strong>bb\")，下标为 3 (\"cac<strong>a</strong>\")\n",
    "\"aba\" -> 下标为 0 (\"<strong>a</strong>cca\")，下标为 2 (\"bb<strong>b</strong>b\")，下标为 3 (\"cac<strong>a</strong>\")\n",
    "\"aba\" -> 下标为 0 (\"<strong>a</strong>cca\")，下标为 1 (\"b<strong>b</strong>bb\")，下标为 3 (\"acc<strong>a</strong>\")\n",
    "\"aba\" -> 下标为 0 (\"<strong>a</strong>cca\")，下标为 2 (\"bb<strong>b</strong>b\")，下标为 3 (\"acc<strong>a</strong>\")\n",
    "\"aba\" -> 下标为 1 (\"c<strong>a</strong>ca\")，下标为 2 (\"bb<strong>b</strong>b\")，下标为 3 (\"acc<strong>a</strong>\")\n",
    "\"aba\" -> 下标为 1 (\"c<strong>a</strong>ca\")，下标为 2 (\"bb<strong>b</strong>b\")，下标为 3 (\"cac<strong>a</strong>\")\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>words = [\"abba\",\"baab\"], target = \"bab\"\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>总共有 4 种不同形成 target 的方法。\n",
    "\"bab\" -> 下标为 0 (\"<strong>b</strong>aab\")，下标为 1 (\"b<strong>a</strong>ab\")，下标为 2 (\"ab<strong>b</strong>a\")\n",
    "\"bab\" -> 下标为 0 (\"<strong>b</strong>aab\")，下标为 1 (\"b<strong>a</strong>ab\")，下标为 3 (\"baa<strong>b</strong>\")\n",
    "\"bab\" -> 下标为 0 (\"<strong>b</strong>aab\")，下标为 2 (\"ba<strong>a</strong>b\")，下标为 3 (\"baa<strong>b</strong>\")\n",
    "\"bab\" -> 下标为 1 (\"a<strong>b</strong>ba\")，下标为 2 (\"ba<strong>a</strong>b\")，下标为 3 (\"baa<strong>b</strong>\")\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>words = [\"abcd\"], target = \"abcd\"\n",
    "<b>输出：</b>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>words = [\"abab\",\"baba\",\"abba\",\"baab\"], target = \"abba\"\n",
    "<b>输出：</b>16\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= words.length <= 1000</code></li>\n",
    "\t<li><code>1 <= words[i].length <= 1000</code></li>\n",
    "\t<li><code>words</code> 中所有单词长度相同。</li>\n",
    "\t<li><code>1 <= target.length <= 1000</code></li>\n",
    "\t<li><code>words[i]</code> 和 <code>target</code> 都仅包含小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-ways-to-form-a-target-string-given-a-dictionary](https://leetcode.cn/problems/number-of-ways-to-form-a-target-string-given-a-dictionary/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-ways-to-form-a-target-string-given-a-dictionary](https://leetcode.cn/problems/number-of-ways-to-form-a-target-string-given-a-dictionary/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"acca\",\"bbbb\",\"caca\"]\\n\"aba\"', '[\"abba\",\"baab\"]\\n\"bab\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        n = len(target)\n",
    "        m, l = len(words), len(words[0])\n",
    "\n",
    "        if l < n:\n",
    "            return 0\n",
    "        \n",
    "        freq = [[0] * 26 for _ in range(l)]\n",
    "\n",
    "        def str_idx(x:str):\n",
    "            return ord(x) - ord('a')\n",
    "\n",
    "        for i in range(l):\n",
    "            for j in range(m):\n",
    "                ch = str_idx(words[j][i])\n",
    "                freq[i][ch] += 1\n",
    "\n",
    "        f = [0] * (n + 1)\n",
    "        f[0] = 1\n",
    "        # f[0] = freq[0][str_idx(target[0])]\n",
    "\n",
    "        for i in range(0, l):\n",
    "            for j in range(n, 0, -1):\n",
    "                f[j] += f[j-1] * freq[i][str_idx(target[j-1])]\n",
    "                f[j] %= MOD\n",
    "\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        \n",
    "        def dfs(dp, cnt, target, i, j, n, m):\n",
    "            if j == m:\n",
    "                return 1\n",
    "            if n - i < m - j:\n",
    "                return 0\n",
    "            if dp[i][j] != -1:\n",
    "                return dp[i][j]\n",
    "            \n",
    "            val = cnt[i][ord(target[j]) - ord('a')] * dfs(dp, cnt, target, i + 1, j + 1, n, m)\n",
    "            val += dfs(dp, cnt, target, i + 1, j, n, m)\n",
    "            val %= mod\n",
    "            dp[i][j] = val\n",
    "            return val\n",
    "        \n",
    "        n = len(words[0])\n",
    "        cnt = [[0] * 26 for _ in range(n)]\n",
    "        for s in words:\n",
    "            for i in range(n):\n",
    "                cnt[i][ord(s[i]) - ord('a')] += 1\n",
    "        \n",
    "        m = len(target)\n",
    "        dp = [[-1] * m for _ in range(n)]\n",
    "        return dfs(dp, cnt, target, 0, 0, n, m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "_MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        l_w, l_t = len(words[0]), len(target)\n",
    "        if l_t > l_w:\n",
    "            return 0\n",
    "        cnts = [Counter([w[i] for w in words]) for i in range(l_w)]\n",
    "        f = [[1 for _ in range(l_w)]]\n",
    "        for i in range(1, l_t + 1):\n",
    "            f.append([(f[i - 1][0] * cnts[i - 1][target[i - 1]]) % _MOD])\n",
    "            for j in range(1, l_w - i + 1):\n",
    "                f[i].append((f[i - 1][j] * cnts[i + j - 1][target[i - 1]] + f[i][j - 1]) % _MOD)\n",
    "        return f[l_t][l_w - l_t]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "\n",
    "        MOD = 10**9 + 7\n",
    "        m, n = len(words), len(target)\n",
    "        l = len(words[0])\n",
    "\n",
    "        # Count of each character in each position of words\n",
    "        counts = [[0] * 26 for _ in range(l)]\n",
    "        for word in words:\n",
    "            for i, c in enumerate(word):\n",
    "                counts[i][ord(c) - ord('a')] += 1\n",
    "\n",
    "        # DP array initialization\n",
    "        dp = [[0] * l for _ in range(n)]\n",
    "        dp[0][0] = counts[0][ord(target[0]) - ord('a')]\n",
    "\n",
    "        # DP transition\n",
    "        for j in range(1, l):\n",
    "            dp[0][j] = dp[0][j - 1] + counts[j][ord(target[0]) - ord('a')]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(i, l):\n",
    "                dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1] * counts[j][ord(target[i]) - ord('a')]\n",
    "                dp[i][j] %= MOD\n",
    "\n",
    "        return dp[n - 1][l - 1]\n",
    "\n",
    "\n",
    "        # 题目意思：words里面选取的顺序并不重要，但是我们选取的第几个字母是需要单调递增的一个特点\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        \n",
    "        # 计算字符在每个位置的频率\n",
    "        freq = [[0] * 26 for _ in range(len(words[0]))]\n",
    "        for word in words:\n",
    "            for j, char in enumerate(word):\n",
    "                freq[j][ord(char) - ord('a')] += 1\n",
    "\n",
    "        # 初始化动态规划数组\n",
    "        m, n = len(target), len(words[0])\n",
    "        dp = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for j in range(n + 1):\n",
    "            dp[0][j] = 1\n",
    "\n",
    "        # 动态规划计算\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1] * freq[j - 1][ord(target[i - 1]) - ord('a')]\n",
    "                dp[i][j] %= mod\n",
    "\n",
    "        return dp[m][n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "\n",
    "        MOD = 10**9 + 7\n",
    "        m, n = len(words), len(target)\n",
    "        l = len(words[0])\n",
    "\n",
    "        # Count of each character in each position of words\n",
    "        counts = [[0] * 26 for _ in range(l)]\n",
    "        for word in words:\n",
    "            for i, c in enumerate(word):\n",
    "                counts[i][ord(c) - ord('a')] += 1\n",
    "\n",
    "        # DP array initialization\n",
    "        dp = [[0] * l for _ in range(n)]\n",
    "        dp[0][0] = counts[0][ord(target[0]) - ord('a')]\n",
    "\n",
    "        # DP transition\n",
    "        for j in range(1, l):\n",
    "            dp[0][j] = dp[0][j - 1] + counts[j][ord(target[0]) - ord('a')]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(i, l):\n",
    "                dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1] * counts[j][ord(target[i]) - ord('a')]\n",
    "                dp[i][j] %= MOD\n",
    "\n",
    "        return dp[n - 1][l - 1]\n",
    "\n",
    "        # # Test cases\n",
    "        # words1 = [\"acca\",\"bbbb\",\"caca\"]\n",
    "        # target1 = \"aba\"\n",
    "        # print(numWays(words1, target\n",
    "\n",
    "\n",
    "        # 题目意思：words里面选取的顺序并不重要，但是我们选取的第几个字母是需要单调递增的一个特点\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(target)\n",
    "        m = len(words[0])\n",
    "        if n > m:\n",
    "            return 0\n",
    "        #记录idx位上字母出现次数\n",
    "        freq = [[0] * 26 for _ in range(m)]\n",
    "        for word in words:\n",
    "            for i in range(len(word)):\n",
    "                idx = ord(word[i]) - ord('a')\n",
    "                freq[i][idx] += 1\n",
    "        #dp[i][j] target中前j个字符与字典中前i个字匹配的方案数\n",
    "        dp = [[0] * m for _ in range(n)]\n",
    "        dp[0][0] = freq[0][ord(target[0]) - ord('a')]\n",
    "        for j in range(1,m):\n",
    "            dp[0][j] += dp[0][j - 1] + freq[j][ord(target[0]) - ord('a')]\n",
    "        for i in range(1,n):\n",
    "            idx = ord(target[i]) - ord('a')\n",
    "            for j in range(i,m):\n",
    "                dp[i][j] = (dp[i - 1][j - 1] * freq[j][idx] + dp[i][j - 1]) % MOD\n",
    "        return dp[n -1][m - 1]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(target)\n",
    "        m = len(words[0])\n",
    "        if n > m:\n",
    "            return 0\n",
    "\n",
    "        #记录idx位上字母出现次数\n",
    "        freq = [[0] * 26 for _ in range(m)]\n",
    "        for word in words:\n",
    "            for i in range(m):\n",
    "                idx = ord(word[i]) - ord('a')\n",
    "                freq[i][idx] += 1\n",
    "        \n",
    "        #dp[i][j] 字典中前j个字符与target中前i个字匹配的方案数\n",
    "        dp = [[0] * (m + 1) for _ in range(n + 1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1,n + 1):\n",
    "            idx = ord(target[i - 1]) - ord('a')\n",
    "            for j in range(i,m + 1):\n",
    "                dp[0][j] = 1\n",
    "                dp[i][j] = (dp[i - 1][j - 1] * freq[j - 1][idx] + dp[i][j - 1]) % MOD\n",
    "        return dp[n][m]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(target)\n",
    "        m = len(words[0])\n",
    "        if n > m:\n",
    "            return 0\n",
    "\n",
    "        #记录idx位上字母出现次数\n",
    "        freq = [[0] * 26 for _ in range(m)]\n",
    "        for word in words:\n",
    "            for i in range(m):\n",
    "                idx = ord(word[i]) - ord('a')\n",
    "                freq[i][idx] += 1\n",
    "        \n",
    "        #dp[i][j] target中前j个字符与字典中前i个字匹配的方案数\n",
    "        dp = [[0] * (m + 1) for _ in range(n + 1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1,n + 1):\n",
    "            idx = ord(target[i - 1]) - ord('a')\n",
    "            for j in range(1,m + 1):\n",
    "                dp[0][j] = 1\n",
    "                dp[i][j] = (dp[i - 1][j - 1] * freq[j - 1][idx] + dp[i][j - 1]) % MOD\n",
    "        return dp[n][m]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10**9+7\n",
    "        n,m = len(words),len(words[0])\n",
    "        t = len(target)\n",
    "        if m<t: return 0\n",
    "        cot = [Counter([e[i] for e in words]) for i in range(m)]\n",
    "        # dp[i][j]表示用words[i:]组成target[j:]的方案数\n",
    "        dp = [[0]*t for _ in range(m)]\n",
    "        dp[m-1][t-1] = 0 if target[-1] not in cot[m-1] else cot[m-1][target[-1]]\n",
    "        for i in range(m-2, -1, -1):\n",
    "            dp[i][t-1] = cot[i][target[t-1]] + dp[i+1][t-1]\n",
    "        for i in range(m-2, -1, -1):\n",
    "            for j in range(t-2, -1, -1):\n",
    "                dp[i][j] = dp[i+1][j] + cot[i][target[j]]*dp[i+1][j+1]\n",
    "                dp[i][j]%=MOD\n",
    "        return dp[0][0]%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n, m = len(target), len(words[0])\n",
    "        count = [[0] * 26 for _ in range(m)]  # count[i][j] 统计每个单词第i个字母的ord是j的数目\n",
    "        for i in range(m):\n",
    "            for w in words:\n",
    "                count[i][ord(w[i]) - ord('a')] += 1\n",
    "        dp = [[0] * m for _ in range(n)]  # dp[i][j] 表示由每个单词的前j个字母，组成target的前i个字母的所有可能\n",
    "        dp[0][0] = sum(1 for w in words if w[0] == target[0])\n",
    "        for i in range(n):\n",
    "            for j in range(i, m):  # i <= j\n",
    "                if j == 0 == i: continue\n",
    "                if i == 0:\n",
    "                    dp[i][j] = dp[i][j - 1] + count[j][ord(target[0]) - ord('a')]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1] * count[j][ord(target[i]) - ord('a')]\n",
    "                dp[i][j] %= MOD\n",
    "\n",
    "        # print(dp)\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(target)\n",
    "        m = len(words[0])\n",
    "        if n > m:\n",
    "            return 0\n",
    "\n",
    "        #记录idx位上字母出现次数\n",
    "        freq = [[0] * 26 for _ in range(m)]\n",
    "        for word in words:\n",
    "            for i in range(m):\n",
    "                idx = ord(word[i]) - ord('a')\n",
    "                freq[i][idx] += 1\n",
    "        \n",
    "        #dp[i][j] 字典中前j个字符与target中前i个字匹配的方案数\n",
    "        dp = [[0] * (m + 1) for _ in range(n + 1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1,n + 1):\n",
    "            idx = ord(target[i - 1]) - ord('a')\n",
    "            for j in range(i,m + 1):\n",
    "                dp[0][j] = 1\n",
    "                dp[i][j] = (dp[i - 1][j - 1] * freq[j - 1][idx] + dp[i][j - 1]) % MOD\n",
    "        return dp[n][m]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(target)\n",
    "        m = len(words[0])\n",
    "        if n > m:\n",
    "            return 0\n",
    "\n",
    "        #记录idx位上字母出现次数\n",
    "        freq = [[0] * 26 for _ in range(m)]\n",
    "        for word in words:\n",
    "            for i in range(m):\n",
    "                idx = ord(word[i]) - ord('a')\n",
    "                freq[i][idx] += 1\n",
    "        \n",
    "        #dp[i][j] target中前j个字符与字典中前i个字匹配的方案数\n",
    "        dp = [[0] * (m + 1) for _ in range(n + 1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1,n + 1):\n",
    "            dp[0][i] = 1\n",
    "            idx = ord(target[i - 1]) - ord('a')\n",
    "            for j in range(1,m + 1):\n",
    "                dp[0][j] = 1\n",
    "                dp[i][j] = (dp[i - 1][j - 1] * freq[j - 1][idx] + dp[i][j - 1]) % MOD\n",
    "        return dp[n][m]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        mod = int(1e9+7)\n",
    "        m,n = len(words),len(words[0])\n",
    "        k = len(target)\n",
    "        ct = [Counter() for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                ct[i][words[j][i]] += 1\n",
    "        @cache\n",
    "        def f(x, p):\n",
    "            if n - x < k - p:\n",
    "                return 0\n",
    "            if p == k:\n",
    "                return 1\n",
    "            r = 0\n",
    "            if target[p] in ct[x]:\n",
    "                r = (r + ct[x][target[p]] * f(x+1, p+1)) % mod\n",
    "            r = (r + f(x+1, p)) % mod\n",
    "\n",
    "            return r\n",
    "        ans = f(0, 0)\n",
    "        f.cache_clear()\n",
    "        return ans\n",
    "                \n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        mod = int(1e9+7)\n",
    "        m,n = len(words),len(words[0])\n",
    "        k = len(target)\n",
    "        ct = [Counter() for _ in range(n)]\n",
    "        # ct[i] 表示第i列的字母以及对应的个数\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                ct[i][words[j][i]] += 1\n",
    "        @cache\n",
    "        def f(x, p):\n",
    "            if n - x < k - p:\n",
    "                return 0\n",
    "            if p == k:\n",
    "                return 1\n",
    "            r = 0\n",
    "            # 可以选择第x列作为target[p]\n",
    "            if target[p] in ct[x]:\n",
    "                r = (r + ct[x][target[p]] * f(x+1, p+1)) % mod\n",
    "            # 不选择第x列作为target[p]\n",
    "            r = (r + f(x+1, p)) % mod\n",
    "            return r\n",
    "        ans = f(0, 0)\n",
    "        f.cache_clear()\n",
    "        return ans\n",
    "                \n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# []\n",
    "# [0 => a, b, c]\n",
    "# [1 => c, b, a]\n",
    "# [2 => c, b]\n",
    "# [3 => a, b]\n",
    "# dp[i][j] = dp[i-1][j-1] * pre[i][target[j]] + dp[i-1][j]\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        words_length = len(words[0])\n",
    "        target_length = len(target)\n",
    "        graph = [collections.defaultdict(int) for _ in range(words_length)]\n",
    "        for word in words:\n",
    "            for idx in range(words_length):\n",
    "                graph[idx][word[idx]] += 1\n",
    "        \n",
    "        dp = [[0] * target_length for _ in range(words_length)]\n",
    "        dp[0][0] = graph[0][target[0]]\n",
    "        for i in range(1, words_length):\n",
    "            dp[i][0] = graph[i][target[0]] + dp[i-1][0]\n",
    "            for j in range(1, min(i+1, target_length)):\n",
    "                dp[i][j] = dp[i-1][j-1] * graph[i][target[j]] + dp[i-1][j]\n",
    "                dp[i][j] %= 10**9 + 7\n",
    "        return dp[-1][-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        dct = defaultdict(lambda: defaultdict(int))\n",
    "        n = len(words[0])\n",
    "        for word in words:\n",
    "            for i, w in enumerate(word):\n",
    "                dct[w][i] += 1\n",
    "\n",
    "        m = len(target)\n",
    "        dp = [[0]*(n+1) for _ in range(m+1)]\n",
    "        dp[0][0] = 1\n",
    "        mod = 10**9 + 7\n",
    "        for i in range(m):\n",
    "            dp[i+1][0] = 0\n",
    "            pre = dp[i][0]\n",
    "            for j in range(n):\n",
    "                c = dct[target[i]][j]\n",
    "                dp[i+1][j+1] = (pre*c) % mod\n",
    "                pre += dp[i][j+1]\n",
    "        return sum(dp[-1]) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        from collections import defaultdict\n",
    "        m = len(words[0])\n",
    "        n = len(target)\n",
    "        \n",
    "        if n > m:\n",
    "            return 0\n",
    "\n",
    "        chars = [defaultdict(int) for _ in range(m)]\n",
    "        for w in words:\n",
    "            for i in range(m):\n",
    "                chars[i][w[i]] += 1\n",
    "        \n",
    "        dp = [[0]*n for _ in range(m)]\n",
    "        dp[0][0] = chars[0][target[0]]\n",
    "        for j in range(1,m):\n",
    "            dp[j][0] = dp[j-1][0] + chars[j][target[0]]\n",
    "\n",
    "        for i in range(1,n):\n",
    "            for j in range(i,m):\n",
    "                dp[j][i] = dp[j-1][i] + dp[j-1][i-1]*chars[j][target[i]]\n",
    "                dp[j][i] %= (10**9+7)\n",
    "        \n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = int(1e9 + 7)\n",
    "        m = len(words[0])\n",
    "        cnt = [Counter(row) for row in zip(*words)]\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i,k):\n",
    "            if i == len(target):\n",
    "                return 1\n",
    "            ans = 0\n",
    "            for j in range(k,m):\n",
    "                if m - j < len(target) - i:\n",
    "                    break\n",
    "                if target[i] in cnt[j]:\n",
    "                    ans += cnt[j][target[i]] * dfs(i + 1,j + 1) % MOD\n",
    "                    ans %= MOD\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = int(1e9 + 7)\n",
    "        m = len(words[0])\n",
    "        cnt = [Counter(w[i] for w in words) for i in range(m)]\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i,k):\n",
    "            if i == len(target):\n",
    "                return 1\n",
    "            ans = 0\n",
    "            for j in range(k,m):\n",
    "                if m - j < len(target) - i:\n",
    "                    break\n",
    "                if target[i] in cnt[j]:\n",
    "                    ans += cnt[j][target[i]] * dfs(i + 1,j + 1) % MOD\n",
    "                    ans %= MOD\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = int(1e9 + 7)\n",
    "        m = len(words[0])\n",
    "        cnt = [Counter(row) for row in zip(*words)]\n",
    "        n = len(target)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i,k):\n",
    "            if i == n:\n",
    "                return 1\n",
    "            if m - k < n - i:\n",
    "                return 0\n",
    "            ans = dfs(i,k + 1)\n",
    "            if target[i] in cnt[k]:\n",
    "                ans += cnt[k][target[i]] * dfs(i + 1,k + 1) % MOD\n",
    "                ans %= MOD\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        m, n = len(words),len(words[0])\n",
    "        l = len(target)\n",
    "        g = [Counter() for _ in range(n)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                g[j][words[i][j]] += 1\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if j == l:  return 1\n",
    "            elif n - i < l - j: return 0\n",
    "            if not g[i][target[j]]: return dfs(i + 1, j)\n",
    "            return (dfs(i + 1, j) + g[i][target[j]] * dfs(i + 1, j + 1)) % MOD\n",
    "        return dfs(0,0)\n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        m = len(words)\n",
    "        n = len(words[0])\n",
    "        Count = defaultdict(int)\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                Count[(i, words[j][i])] += 1\n",
    "        l = len(target)\n",
    "        dp = [[0]*l for _ in range(n) ]\n",
    "        dp[0][0] = Count[(0, target[0])]\n",
    "        for i in range(1,n):\n",
    "            dp[i][0] =dp[i-1][0]+ Count[(i, target[0])]%MOD #dp[i-1][j-1],j-1需要大于0\n",
    "            for j in range(1,l):\n",
    "                dp[i][j] = dp[i-1][j] #先加上dp[i-1][j]的匹配完结果数\n",
    "                if (i, target[j]) in Count.keys():#如果当前target[j]在i列中\n",
    "                    dp[i][j] += dp[i-1][j-1]*Count[(i, target[j])]%MOD\n",
    "        # print(dp)\n",
    "        return dp[-1][-1]%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        m = len(words)\n",
    "        n = len(words[0])\n",
    "        Count = defaultdict(int)\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                Count[(i, words[j][i])] += 1\n",
    "        l = len(target)\n",
    "        dp = [[0]*l for _ in range(n) ]\n",
    "        dp[0][0] = Count[(0, target[0])]\n",
    "        print(dp)\n",
    "        for i in range(1,n):\n",
    "            dp[i][0] =dp[i-1][0]+ Count[(i, target[0])]%MOD\n",
    "            for j in range(1,l):\n",
    "                dp[i][j] = dp[i-1][j] #先加上dp[i-1][j]\n",
    "                if (i, target[j]) in Count.keys():#如果当前target[j]在i列中\n",
    "                    dp[i][j] += dp[i-1][j-1]*Count[(i, target[j])]%MOD\n",
    "        # print(dp)\n",
    "        return dp[-1][-1]%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        m = len(words)\n",
    "        n = len(words[0])\n",
    "        Count = defaultdict(int)\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                Count[(i, words[j][i])] += 1\n",
    "        l = len(target)\n",
    "        dp = [[0]*l for _ in range(n) ]\n",
    "        dp[0][0] = Count[(0, target[0])]\n",
    "        print(dp)\n",
    "        for i in range(1,n):\n",
    "            dp[i][0] =dp[i-1][0]+ Count[(i, target[0])]%MOD\n",
    "            for j in range(1,l):\n",
    "                dp[i][j] = dp[i-1][j] #先加上dp[i-1][j]\n",
    "                if (i, target[j]) in Count.keys():#如果当前target[j]在i列中\n",
    "                    dp[i][j] += dp[i-1][j-1]*Count[(i, target[j])]%MOD\n",
    "        # print(dp)\n",
    "        return dp[-1][-1]%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        m, n = len(words), len(words[0])\n",
    "        l = len(target)\n",
    "        d = [{} for i in range(n)]#哈希表数组\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                c = words[i][j]\n",
    "                d[j][c] = d[j].get(c, 0) + 1\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j):#words字符下标，target字符下标\n",
    "            if j == l:#target遍历完，可行\n",
    "                return 1\n",
    "            elif n - i < l - j:#words中的剩余字符数量小于target的剩余字符数量，方案不可行\n",
    "                return 0\n",
    "            if target[j] not in d[i]:#如果不存在哈希表中\n",
    "                return dfs(i + 1, j)\n",
    "            return (dfs(i + 1, j) + d[i][target[j]] * dfs(i + 1, j + 1)) % mod\n",
    "        mod = 10 ** 9 + 7\n",
    "        return dfs(0, 0)\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "       MOD = 10 ** 9 + 7\n",
    "       @cache\n",
    "       def dfs(i: int, j: int) -> int:\n",
    "          if i == len(target):\n",
    "             return 1\n",
    "          if j == n:\n",
    "             return 0\n",
    "          if len(target) - i > n - j:\n",
    "             return 0\n",
    "          return (dfs(i, j + 1) + cnts[j][ord(target[i]) - ord('a')] * dfs(i + 1, j + 1)) % MOD\n",
    "       n = len(words[0])\n",
    "       cnts = [[0] * 26 for _ in range(n)]\n",
    "       for w in words:\n",
    "          for i, c in enumerate(w):\n",
    "             cnts[i][ord(c) - ord('a')] += 1\n",
    "       return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(target)\n",
    "        m = len(words)\n",
    "        p = len(words[0])\n",
    "\n",
    "        cnt = [[0] * 26 for _ in range(p)]\n",
    "        for i in range(m):\n",
    "            for j in range(p):\n",
    "                cnt[j][ord(words[i][j]) - ord('a')] += 1\n",
    "        \n",
    "        @cache\n",
    "        def compute(i,j):\n",
    "            if j == n:\n",
    "                return 1\n",
    "            if p - i < n - j:\n",
    "                return 0\n",
    "            \n",
    "            return (compute(i+1,j) + compute(i+1,j+1)*cnt[i][ord(target[j])-ord('a')])%MOD\n",
    "\n",
    "        return compute(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        n, m = len(target), len(words[0])\n",
    "        rec = [[0] * 26 for _ in range(m)]\n",
    "        for w in words:\n",
    "            for i in range(m):\n",
    "                rec[i][ord(w[i]) - ord('a')] += 1\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i < 0:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for k in range(i, j + 1):\n",
    "                if rec[k][ord(target[i]) - ord('a')]:\n",
    "                    res += rec[k][ord(target[i]) - ord('a')] * dfs(i - 1, k - 1)\n",
    "                    res %= MOD\n",
    "            return res\n",
    "        return dfs(n - 1, m - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        n = len(words[0])\n",
    "        MOD = 10 ** 9 + 7\n",
    "        d = [[0] * 26 for _ in range(n)]\n",
    "        for i in words:\n",
    "            for j,c in enumerate(i):\n",
    "                d[j][ord(c) - 97] += 1\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(m,k):\n",
    "            mval = ord(target[m-1]) - 97\n",
    "            if m == 1:\n",
    "                return d[k][mval]\n",
    "            if k+1 < m:\n",
    "                return 0\n",
    "            \n",
    "            c = 0\n",
    "            for i in range(m-2, k):\n",
    "                c = (c + d[k][mval] * dp(m-1,i)) % MOD\n",
    "            # print(m,k,c, mval, d[k][mval])\n",
    "            return c\n",
    "        return sum([dp(len(target), i) for i in range(n)]) % MOD\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(target)\n",
    "        m = len(words[0])\n",
    "        if n > m:\n",
    "            return 0\n",
    "        #记录idx位上字母出现次数\n",
    "        freq = [[0] * 26 for _ in range(m)]\n",
    "        for word in words:\n",
    "            for i in range(len(word)):\n",
    "                idx = ord(word[i]) - ord('a')\n",
    "                freq[i][idx] += 1\n",
    "        @cache\n",
    "        def dfs(idx,k) -> int:\n",
    "            if idx == n:\n",
    "                return 1\n",
    "            res = 0\n",
    "            num = ord(target[idx]) - ord('a')\n",
    "            for i in range(k,m):\n",
    "                if freq[i][num]:\n",
    "                    res += freq[i][num] * dfs(idx + 1,i + 1) % MOD\n",
    "                if m - i < n - idx:\n",
    "                    break\n",
    "            return res % MOD\n",
    "        return dfs(0,0)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache\n",
    "    def build(self, i, k):\n",
    "        if self.l-k < self.t-i:\n",
    "            return 0\n",
    "\n",
    "        if i == self.t:\n",
    "            return 1\n",
    "\n",
    "        if i*(self.l+1)+k in self.d:\n",
    "            return self.d[i*(self.l+1)+k]\n",
    "        \n",
    "        r = self.rec[k][ord(self.target[i])-ord(\"a\")]*self.build(i+1, k+1) + self.build(i, k+1)\n",
    "        self.d[i*(self.l+1)+k] = r\n",
    "        return r\n",
    "\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        n = len(words)\n",
    "        self.t = t = len(target)\n",
    "        self.target = target\n",
    "        self.l = l = len(words[0])\n",
    "        self.rec = rec = [[0]*26 for _ in range(l)]\n",
    "        for i in range(n):\n",
    "            for j in range(l):\n",
    "                rec[j][ord(words[i][j])-ord(\"a\")] += 1\n",
    "\n",
    "        self.d = {}\n",
    "        return self.build(0, 0) % (10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        cts = []\n",
    "        for i in range(len(words[0])):\n",
    "            cts.append(collections.Counter(words[j][i] for j in range(len(words))))\n",
    "            \n",
    "        n = len(cts)\n",
    "                    \n",
    "        @lru_cache(None)\n",
    "        def dfs(cur, t):\n",
    "            if len(t) > n - cur:\n",
    "                return 0\n",
    "                \n",
    "            if not t:\n",
    "                return 1\n",
    "                \n",
    "            return (dfs(cur+1, t) + cts[cur][t[0]] * dfs(cur+1, t[1:])) % (10**9 + 7)\n",
    "        \n",
    "        return dfs(0, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        m,n = len(words[0]),len(target)\n",
    "        \n",
    "        # 存储每列上的元素个数\n",
    "        index_count = [Counter(w[i] for w in words) for i in range(len(words[0]))]\n",
    "      \n",
    "        @lru_cache(None)\n",
    "        def dfs(index,k):\n",
    "            if index == n:\n",
    "                return 1\n",
    "            if k == m:\n",
    "                return 0\n",
    "            res = dfs(index,k + 1)\n",
    "            if target[index] in index_count[k]:\n",
    "                res += index_count[k][target[index]] * dfs(index + 1,k + 1) % mod\n",
    "                res %= mod\n",
    "            return res\n",
    "        \n",
    "        return dfs(0,0) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        ans = 0\n",
    "        n = len(words[0])\n",
    "        m = len(target)\n",
    "        pos = [Counter(w[i] for w in words) for i in range(len(words[0]))]\n",
    "\n",
    "        @cache\n",
    "        def dfs(p, w):\n",
    "            if w == len(target): return 1\n",
    "            if p == n: return 0\n",
    "            res = dfs(p + 1, w)\n",
    "            if target[w] in pos[p]: \n",
    "                res = (res + dfs(p + 1, w + 1) * pos[p][target[w]]) % MOD\n",
    "            return res\n",
    "        return dfs(0, 0) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays1(self, words: List[str], target: str) -> int:\n",
    "        n=len(words[0])\n",
    "        m=len(words)\n",
    "        dic_lst=[Counter([words[i][k] for i in range(m)]) for k in range(n)]\n",
    "        t=len(target)\n",
    "        dp=[[0]*t for i in range(n)]\n",
    "        cur=0\n",
    "        for i in range(n):\n",
    "            if target[0] in dic_lst[i]:\n",
    "                cur+=dic_lst[i][target[0]]\n",
    "            dp[i][0]=cur\n",
    "        for i in range(1,n):\n",
    "            for k in range(1,t):\n",
    "                if target[k] in dic_lst[i]:\n",
    "                    dp[i][k]=dic_lst[i][target[k]]*dp[i-1][k-1]+dp[i-1][k]\n",
    "                else:\n",
    "                    dp[i][k]=dp[i-1][k]\n",
    "        return dp[-1][-1]%(10**9+7)\n",
    "\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        m,n = len(words[0]),len(target)\n",
    "        \n",
    "        # 存储每列上的元素个数\n",
    "        index_count = [Counter(w[i] for w in words) for i in range(len(words[0]))]\n",
    "      \n",
    "        @lru_cache(None)\n",
    "        def dfs(index,k):\n",
    "            if index == n:\n",
    "                return 1\n",
    "            if k == m:\n",
    "                return 0\n",
    "            res = dfs(index,k + 1)\n",
    "            if target[index] in index_count[k]:\n",
    "                res += index_count[k][target[index]] * dfs(index + 1,k + 1)\n",
    "            return res\n",
    "        \n",
    "        return dfs(0,0) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        m,n = len(words[0]),len(target)\n",
    "        \n",
    "        # 存储每列上的元素个数\n",
    "        index_count = [Counter(w[i] for w in words) for i in range(len(words[0]))]\n",
    "      \n",
    "        @lru_cache(None)\n",
    "        def dfs(index,k):\n",
    "            if index == n:\n",
    "                return 1\n",
    "            if k == m:\n",
    "                return 0\n",
    "            res = dfs(index,k + 1)\n",
    "            if target[index] in index_count[k]:\n",
    "                res += index_count[k][target[index]] * dfs(index + 1,k + 1)\n",
    "            return res\n",
    "        \n",
    "        return dfs(0,0) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "       MOD = 10 ** 9 + 7\n",
    "       @cache\n",
    "       def dfs(i: int, j: int) -> int:\n",
    "          if i == len(target):\n",
    "             return 1\n",
    "          if j == n:\n",
    "             return 0\n",
    "          return (dfs(i, j + 1) + cnts[j][ord(target[i]) - ord('a')] * dfs(i + 1, j + 1)) % MOD\n",
    "       n = len(words[0])\n",
    "       if len(target) > n:\n",
    "          return 0\n",
    "       cnts = [[0] * 26 for _ in range(n)]\n",
    "       for w in words:\n",
    "          for i, c in enumerate(w):\n",
    "             cnts[i][ord(c) - ord('a')] += 1\n",
    "       return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "       MOD = 10 ** 9 + 7\n",
    "       @cache\n",
    "       def dfs(i: int, j: int) -> int:\n",
    "          if i == len(target):\n",
    "             return 1\n",
    "          if j == n:\n",
    "             return 0\n",
    "          res = dfs(i, j + 1) + cnts[j][ord(target[i]) - ord('a')] * dfs(i + 1, j + 1)\n",
    "          res %= MOD\n",
    "          return res\n",
    "         #  if cnts[j][ord(target[i]) - ord('0')] > 0:\n",
    "         #     res += cnts[j][ord(target[i]) - ord('0')] * dfs(i + 1, j + 1)\n",
    "          \n",
    "       n = len(words[0])\n",
    "       if len(target) > n:\n",
    "          return 0\n",
    "       cnts = [[0] * 26 for _ in range(n)]\n",
    "       for w in words:\n",
    "          for i, c in enumerate(w):\n",
    "             cnts[i][ord(c) - ord('a')] += 1\n",
    "       return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10**9+7\n",
    "        lw, ls = len(words), len(words[0])\n",
    "        lt = len(target)\n",
    "        dic = [[0]*26 for _ in range(ls)]\n",
    "\n",
    "        for i in range(ls):\n",
    "            for j in range(lw):\n",
    "                dic[i][(ord(words[j][i]) & 31) - 1] += 1\n",
    "\n",
    "        @cache\n",
    "        def fun(nows, nowt):\n",
    "            if nowt == lt:\n",
    "                return 1\n",
    "            if nows == ls:\n",
    "                return 0\n",
    "            return dic[nows][(ord(target[nowt]) & 31) - 1]*fun(nows+1, nowt+1) + fun(nows+1, nowt)\n",
    "        \n",
    "        return fun(0, 0) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "\n",
    "        n = len(words[0])\n",
    "        m = len(words)\n",
    "        dic_lst = [Counter([words[i][k] for i in range(m)]) for k in range(n)]\n",
    "        t = len(target)\n",
    "        dp = [[0] * t for i in range(n)]\n",
    "        cur = 0\n",
    "        \n",
    "        for i in range(n):\n",
    "            if target[0] in dic_lst[i]:\n",
    "                cur += dic_lst[i][target[0]]\n",
    "            dp[i][0] = cur\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            for k in range(1, t):\n",
    "                if target[k] in dic_lst[i]:\n",
    "                    dp[i][k] = dic_lst[i][target[k]] * dp[i-1][k-1] + dp[i-1][k]\n",
    "                else:\n",
    "                    dp[i][k] = dp[i-1][k]\n",
    "        \n",
    "        return dp[-1][-1] % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        MOD = 10**9+7\n",
    "        lw, ls = len(words), len(words[0])\n",
    "        lt = len(target)\n",
    "        dic = [[0]*26 for _ in range(ls)]\n",
    "\n",
    "        for i in range(ls):\n",
    "            for j in range(lw):\n",
    "                dic[i][(ord(words[j][i]) & 31) - 1] += 1\n",
    "        \n",
    "        dp = [[0]*lt + [1] for _ in range(ls+1)]\n",
    "        for nowt in range(lt-1, -1, -1):\n",
    "            for nows in range(ls-1, -1, -1):\n",
    "                dp[nows][nowt] = dic[nows][(ord(target[nowt]) & 31) - 1]*dp[nows+1][nowt+1] + dp[nows+1][nowt]\n",
    "        return dp[0][0] % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        m, n = len(target), len(words[0])\n",
    "        word_chars = []\n",
    "        for i in range(n):\n",
    "            word_chars.append(collections.Counter(word[i] for word in words))\n",
    "        \n",
    "        # dp[i][j] = # of ways to form target[:i] using words[:j]\n",
    "        dp = [[0] * (n+1) for _ in range(m+1)]\n",
    "        for i in range(n+1): dp[0][i] = 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dp[i+1][j+1] = word_chars[j][target[i]] * dp[i][j] + dp[i+1][j]\n",
    "\n",
    "        return dp[-1][-1] % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        m, n, t = len(words), len(words[0]), len(target)\n",
    "        d = [Counter([x[k] for x in words]) for k in range(n)]\n",
    "        dp = [[0] * t for _ in range(n)]\n",
    "        cur = 0\n",
    "        for i in range(n):\n",
    "            x = target[0] \n",
    "            if x in d[i]:\n",
    "                cur += d[i][x]\n",
    "            dp[i][0] = cur\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, t):\n",
    "                c = target[j]\n",
    "                if c in d[i]:\n",
    "                    dp[i][j] = dp[i-1][j] + dp[i-1][j-1] * d[i][c]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "        return dp[-1][-1] % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        n = len(words[0])\n",
    "        m = len(target)\n",
    "        l = len(words)\n",
    "        dp = [[0 for _ in range(m)] for __ in range(n)]\n",
    "        coef=[Counter([words[i][k] for i in range(l)]) for k in range(n)]\n",
    "        cur = 0\n",
    "        for i in range(n):\n",
    "            cur_s = target[0]\n",
    "            if cur_s in coef[i]:\n",
    "                cur += coef[i][cur_s]\n",
    "            dp[i][0] = cur\n",
    "        for t in range(1,m):\n",
    "            cur_s = target[t]\n",
    "            for i in range(1,n):\n",
    "                if cur_s in coef[i]:\n",
    "                    dp[i][t] = coef[i][cur_s]*dp[i-1][t-1] + dp[i-1][t]\n",
    "                \n",
    "                else:\n",
    "                    dp[i][t] = dp[i-1][t]\n",
    "        \n",
    "        return int(dp[-1][-1] % (10**9 + 7))\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        n1 = len(words[0])\n",
    "        cnt = []\n",
    "        for i in range(n1):\n",
    "            dict_tmp = {}\n",
    "            for k in range(26):\n",
    "                dict_tmp[chr(97+k)] = 0\n",
    "            for j in range(len(words)):\n",
    "                dict_tmp[words[j][i]] += 1\n",
    "                    # dict_tmp[words[j][i]] % mod\n",
    "            cnt.append(dict_tmp)\n",
    "        # print(words)\n",
    "        # print(target)\n",
    "        # print(cnt)\n",
    "        dp = [[0 for _ in range(len(target)+1)] for _ in range(n1+1)]\n",
    "\n",
    "        # dp[i][j]: 第i位词典字符起，target从第j个开始到最后, i, j 从第0个开始计数\n",
    "        # dp[i][j] = dp[i+1]dp[j] + dp[i+1]dp[j+1] * cnt[i-1][target[j-1]]\n",
    "        dp[n1-1][len(target)-1] = cnt[n1 - 1][target[-1]]\n",
    "        # print(dp)\n",
    "        for i in range(n1-1, -1, -1):\n",
    "            dp[i][len(target)-1] = cnt[i][target[-1]] + dp[i+1][len(target)-1]\n",
    "            # dp[i][len(target)-1] %= mod\n",
    "        # print(dp)\n",
    "        for i in range(n1-1, -1, -1):\n",
    "            # for j in range(1, len(target)+1):\n",
    "            for j in range(len(target)-2, -1, -1):\n",
    "                dp[i][j] = dp[i+1][j] + dp[i+1][j+1] * cnt[i][target[j]]\n",
    "                # dp[i][j] %= mod\n",
    "        # print(dp)\n",
    "        return dp[0][0] % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 1000000007\n",
    "class Solution:\n",
    "    def numWays(self, words: List[str], target: str) -> int:\n",
    "        d = defaultdict(lambda :0)\n",
    "        for w in words:\n",
    "            for i,x in enumerate(w):\n",
    "                d[(i,x)]+=1\n",
    "        \n",
    "        n = len(words[0])\n",
    "        m = len(target)\n",
    "        @cache \n",
    "        def f(x,y):\n",
    "            if x >= n:\n",
    "                return 0\n",
    "            if y == m-1:\n",
    "                return (d[(x,target[y])] + f(x+1, y)) % mod\n",
    "            return (d[(x,target[y])] * f(x+1,y+1) + f(x+1,y)) % mod\n",
    "            \n",
    "        return f(0,0)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
